{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Recover Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: recoverTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #恢复二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉搜索树的根节点 <code>root</code> ，该树中的 <strong>恰好</strong> 两个节点的值被错误地交换。<em>请在不改变其结构的情况下，恢复这棵树&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/28/recover1.jpg\" style=\"width: 300px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,3,null,null,2]\n",
    "<strong>输出：</strong>[3,1,null,null,2]\n",
    "<strong>解释：</strong>3 不能是 1 的左孩子，因为 3 &gt; 1 。交换 1 和 3 使二叉搜索树有效。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/28/recover2.jpg\" style=\"height: 208px; width: 400px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,1,4,null,null,2]\n",
    "<strong>输出：</strong>[2,1,4,null,null,3]\n",
    "<strong>解释：</strong>2 不能在 3 的右子树中，因为 2 &lt; 3 。交换 2 和 3 使二叉搜索树有效。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树上节点的数目在范围 <code>[2, 1000]</code> 内</li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= Node.val &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>使用 <code>O(n)</code> 空间复杂度的解法很容易实现。你能想出一个只使用&nbsp;<code>O(1)</code> 空间的解决方案吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [recover-binary-search-tree](https://leetcode.cn/problems/recover-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [recover-binary-search-tree](https://leetcode.cn/problems/recover-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,null,null,2]', '[3,1,4,null,null,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def findWrongPairs(\n",
    "        self, node: TreeNode, p_succ: TreeNode, pairs: List[List[TreeNode]]\n",
    "    ) -> TreeNode:\n",
    "        if node is None:\n",
    "            return None\n",
    "        \n",
    "        left_min: Optional[TreeNode] = self.findWrongPairs(node.left, node, pairs)\n",
    "        right_min: Optional[TreeNode] = self.findWrongPairs(node.right, p_succ, pairs)\n",
    "        succ: Optional[TreeNode] = None\n",
    "\n",
    "        succ = right_min if right_min is not None else p_succ\n",
    "        if succ is not None and node.val > succ.val:\n",
    "            pairs.append([node, succ])\n",
    "\n",
    "        return left_min if left_min is not None else node\n",
    "\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        pairs: List[List[TreeNode]] = []\n",
    "        self.findWrongPairs(root, None, pairs)\n",
    "        pairs.sort(key=lambda wp: wp[0].val, reverse=True)\n",
    "        \n",
    "        if len(pairs) == 1:\n",
    "            pairs[0][0].val, pairs[0][1].val = pairs[0][1].val, pairs[0][0].val\n",
    "        else:\n",
    "            pairs[0][0].val, pairs[1][1].val = pairs[1][1].val, pairs[0][0].val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        cur, pre = root, None\n",
    "        first, second = None, None\n",
    "        stack = []\n",
    "        \n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:        \n",
    "                node = stack.pop()\n",
    "                if pre and pre.val >= node.val:\n",
    "                    if not first:\n",
    "                        first = pre\n",
    "                    second = node\n",
    "                    \n",
    "                pre = node\n",
    "                cur = node.right\n",
    "        \n",
    "        first.val, second.val = second.val, first.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        def inorder(node):\n",
    "            if node:\n",
    "                inorder(node.left)\n",
    "                if self.prev.val > node.val:\n",
    "                    if not self.a:\n",
    "                        self.a = self.prev\n",
    "                    self.b = node\n",
    "                self.prev = node\n",
    "                inorder(node.right)\n",
    "        self.prev, self.a, self.b = TreeNode(float('-inf')), None, None\n",
    "        inorder(root)\n",
    "        self.a.val, self.b.val = self.b.val, self.a.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def recursive(self,root,inorder_traversal):\n",
    "        if root.left != None:\n",
    "            self.recursive(root.left,inorder_traversal)\n",
    "        inorder_traversal.append(root.val)\n",
    "        if root.right != None:\n",
    "            self.recursive(root.right,inorder_traversal)\n",
    "    def inorderTraversal(self, root):\n",
    "        inorder_traversal = []\n",
    "        if root:\n",
    "            self.recursive(root,inorder_traversal)\n",
    "        return inorder_traversal\n",
    "    def recoverTree(self, root):\n",
    "        inorder_traversal = self.inorderTraversal(root)\n",
    "        wrong = []\n",
    "        inorder_sort = sorted(inorder_traversal)\n",
    "        for i in range(len(inorder_traversal)):\n",
    "            if inorder_traversal[i] != inorder_sort[i]:\n",
    "                wrong.append(inorder_traversal[i])\n",
    "        result, stack = [], [(root, False)]\n",
    "\n",
    "        while stack:\n",
    "            cur, visited = stack.pop()\n",
    "            if cur:\n",
    "                if visited:\n",
    "                    if cur.val == wrong[0]:\n",
    "                        cur.val = wrong[1]\n",
    "                    elif cur.val == wrong[1]:\n",
    "                        cur.val = wrong[0]\n",
    "                else:\n",
    "                    stack.append((cur.right, False))\n",
    "                    stack.append((cur, True))\n",
    "                    stack.append((cur.left, False))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root):\n",
    "        \"\"\"\n",
    "        :通过遍历修改值\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        l = []\n",
    "        Solution.i1 = Solution.i2 = Solution.i =  -1\n",
    "        Solution.tmp = - 2147483648\n",
    "        self.check(root)\n",
    "        if Solution.i1<0:\n",
    "            return\n",
    "        if Solution.i2<0:\n",
    "            Solution.i2 = Solution.i1+1\n",
    "        print(Solution.i1)\n",
    "        print(Solution.i2)\n",
    "        Solution.i = -1\n",
    "        self.recover(root)\n",
    "            \n",
    "        \n",
    "        \n",
    "    def check(self,root):\n",
    "        if root==None:\n",
    "            return\n",
    "        self.check(root.left)\n",
    "        Solution.i+=1\n",
    "        if root.val<Solution.tmp:\n",
    "            if Solution.i1<0:\n",
    "                Solution.i1 = Solution.i-1\n",
    "                Solution.v2 = root.val\n",
    "            else:\n",
    "                Solution.i2 = Solution.i\n",
    "                Solution.v2 = root.val\n",
    "        Solution.tmp = root.val\n",
    "        self.check(root.right)\n",
    "        \n",
    "    def recover(self,root):\n",
    "        if root==None:\n",
    "            return\n",
    "        self.recover(root.left)\n",
    "        \n",
    "        Solution.i+=1\n",
    "        if Solution.i==Solution.i1:\n",
    "            Solution.v1 = root.val\n",
    "            root.val = Solution.v2\n",
    "            \n",
    "        if Solution.i==Solution.i2:\n",
    "            root.val = Solution.v1\n",
    "            \n",
    "        self.recover(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root):\n",
    "        l = []\n",
    "        l_plus = []\n",
    "        self.dfs(root, l, l_plus)\n",
    "        l_plus = sorted(l_plus)\n",
    "        # print(l_plus)\n",
    "        first =0\n",
    "        second = 0\n",
    "        flag = False\n",
    "        for i in range(len(l)):\n",
    "            # print(l[i].val)\n",
    "            if l_plus[i] != l[i].val:\n",
    "                first = i\n",
    "                print(first)\n",
    "                for j in range(i+1, len(l)):\n",
    "                    if l_plus[i] == l[j].val:\n",
    "                        second = j\n",
    "                        flag = True\n",
    "                if flag:\n",
    "                    break\n",
    "        l[first].val, l[second].val = l[second].val, l[first].val\n",
    "        print(l[first].val, l[second].val)\n",
    "                    \n",
    "\n",
    "\n",
    "    def dfs(self, root, l, l_plus):\n",
    "        if root:\n",
    "            self.dfs(root.left, l, l_plus)\n",
    "            l.append(root)\n",
    "            l_plus.append(root.val)\n",
    "            self.dfs(root.right, l, l_plus)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        maxd, mind = {}, {}\n",
    "        def get_max_node(root):\n",
    "            m = maxd.get(root)\n",
    "            if m:\n",
    "                return m\n",
    "            m = root\n",
    "            if root.left:\n",
    "                ml = get_max_node(root.left)\n",
    "                if ml.val > m.val:\n",
    "                    m = ml\n",
    "            if root.right:\n",
    "                mr = get_max_node(root.right)\n",
    "                if mr.val > m.val:\n",
    "                    m = mr\n",
    "            maxd[root] = m\n",
    "            return m\n",
    "        \n",
    "        def get_min_node(root):\n",
    "            m = mind.get(root)\n",
    "            if m:\n",
    "                return m\n",
    "            m = root\n",
    "            if root.left:\n",
    "                ml = get_min_node(root.left)\n",
    "                if ml.val < m.val:\n",
    "                    m = ml\n",
    "            if root.right:\n",
    "                mr = get_min_node(root.right)\n",
    "                if mr.val < m.val:\n",
    "                    m = mr\n",
    "            mind[root] = m\n",
    "            return m\n",
    "        \n",
    "        st = [root]\n",
    "        while st:\n",
    "            t = st.pop()\n",
    "            maxl, minr = None, None\n",
    "            if t.left:\n",
    "                maxl = get_max_node(t.left)\n",
    "                st.append(t.left)\n",
    "            if t.right:\n",
    "                minr = get_min_node(t.right)\n",
    "                st.append(t.right)\n",
    "            if minr: print(t.val, minr.val)\n",
    "            if maxl and minr and minr.val < t.val < maxl.val:\n",
    "                minr.val, maxl.val = maxl.val, minr.val\n",
    "                break\n",
    "            elif maxl and maxl.val > t.val:\n",
    "                maxl.val, t.val = t.val, maxl.val\n",
    "                break\n",
    "            elif minr and minr.val < t.val:\n",
    "                minr.val, t.val = t.val, minr.val\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        def inorder(root, res, vals):\n",
    "            if not root:\n",
    "                return \n",
    "            inorder(root.left, res, vals)\n",
    "            res.append(root)\n",
    "            vals.append(root.val)\n",
    "            inorder(root.right, res, vals)\n",
    "        res, vals = [], []\n",
    "        inorder(root, res, vals)\n",
    "        vals.sort()\n",
    "        for i in range(len(res)):\n",
    "            res[i].val = vals[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        pre_node = None\n",
    "        curr_node = root\n",
    "        first_node, second_node = None, None\n",
    "        flag = None\n",
    "\n",
    "        while curr_node is not None:\n",
    "            # morris中序遍历\n",
    "            if curr_node.left is not None:\n",
    "                pre_node = curr_node.left\n",
    "                while pre_node.right is not None and pre_node.right != curr_node:\n",
    "                    pre_node = pre_node.right\n",
    "                if pre_node.right is None:\n",
    "                    pre_node.right = curr_node\n",
    "                    curr_node = curr_node.left\n",
    "                    continue\n",
    "                pre_node.right = None\n",
    "\n",
    "            # 错误节点\n",
    "            if flag is not None and flag.val > curr_node.val:\n",
    "                if first_node is None:\n",
    "                    first_node = flag\n",
    "                second_node = curr_node\n",
    "            flag = curr_node\n",
    "            curr_node = curr_node.right\n",
    "\n",
    "        # 交换\n",
    "        first_node.val, second_node.val = second_node.val, first_node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        data = [None, None, None]\n",
    "        def inorder(node):\n",
    "            if not node:\n",
    "                return\n",
    "            inorder(node.left)\n",
    "            if data[2] and data[2].val > node.val:\n",
    "                if not data[0]:\n",
    "                    data[0] = data[2]\n",
    "                data[1] = node\n",
    "            data[2] = node\n",
    "            inorder(node.right)\n",
    "        inorder(root)\n",
    "        data[0].val, data[1].val = data[1].val, data[0].val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        a, b, pre = None, None, None\n",
    "        stack = []\n",
    "        while root or stack:\n",
    "            if root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = stack.pop()\n",
    "                if pre and root.val <= pre.val:\n",
    "                    b = root\n",
    "                    if a is None:\n",
    "                        a = pre\n",
    "                    else:\n",
    "                        break\n",
    "                pre = root\n",
    "                root = root.right\n",
    "\n",
    "        a.val, b.val = b.val, a.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        x = None\n",
    "        y = None\n",
    "        cur = root\n",
    "        pre = None\n",
    "        while cur:\n",
    "            if cur.left == None:\n",
    "                if pre and pre.val > cur.val:\n",
    "                    y = cur\n",
    "                    if x == None:\n",
    "                        x = pre\n",
    "                pre = cur\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                # find right\n",
    "                rright = cur.left\n",
    "                while rright.right and rright.right != cur:\n",
    "                    rright = rright.right\n",
    "                \n",
    "                if rright.right == None:\n",
    "                    rright.right = cur\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    if pre and pre.val > cur.val:\n",
    "                        y = cur\n",
    "                        if x == None:\n",
    "                            x = pre\n",
    "                    pre = cur\n",
    "                    rright.right = None\n",
    "                    cur = cur.right\n",
    "        x.val, y.val = y.val, x.val\n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    nums = []\n",
    "    \n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        nums = []\n",
    "        self.x = -1\n",
    "        self.y = -1\n",
    "        self.inorder(root, nums)\n",
    "        self.findTwoSwappedNums(nums);\n",
    "        self.recover(root)\n",
    "    \n",
    "    def inorder(self, rt: TreeNode, nums: List[int]) -> None:\n",
    "        if rt == None:\n",
    "            return \n",
    "        self.inorder(rt.left, nums)\n",
    "        nums.append(rt.val)\n",
    "        self.inorder(rt.right, nums)\n",
    "\n",
    "    def findTwoSwappedNums(self, nums: List[int]) -> None:\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                self.y = nums[i+1]\n",
    "                if self.x == -1:\n",
    "                    self.x = nums[i]\n",
    "                else:\n",
    "                    break\n",
    "    def recover(self, rt: TreeNode) -> None:\n",
    "        if rt == None:\n",
    "            return \n",
    "        if rt.val == self.x:\n",
    "            rt.val = self.y\n",
    "        elif rt.val == self.y:\n",
    "            rt.val = self.x\n",
    "        self.recover(rt.left)\n",
    "        self.recover(rt.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        nums = []\n",
    "\n",
    "        def walk(node):\n",
    "            if node == None:\n",
    "                return\n",
    "\n",
    "            walk(node.left)\n",
    "            nums.append(node.val)\n",
    "            walk(node.right)\n",
    "\n",
    "        def findSwapNum(arr):\n",
    "            n = len(arr)\n",
    "            x = y = -1\n",
    "\n",
    "            for i in range(n - 1):\n",
    "                if arr[i + 1] < arr[i]:\n",
    "                    y = arr[i + 1]\n",
    "\n",
    "                    if x == -1:\n",
    "                        x = nums[i]\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "            return [x, y]\n",
    "\n",
    "        def recover(r, count, x, y):\n",
    "            if r != None:\n",
    "                if r.val == x or r.val == y:\n",
    "                    r.val = y if r.val == x else x\n",
    "\n",
    "                    if --count == 0:\n",
    "                        return\n",
    "\n",
    "                recover(r.left, count, x, y);\n",
    "                recover(r.right, count, x, y);\n",
    "\n",
    "        walk(root)\n",
    "\n",
    "        swapNums = findSwapNum(nums)\n",
    "        recover(root, 2, swapNums[0], swapNums[1]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        stack = []\n",
    "        def midPut(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.left:\n",
    "                midPut(node.left)\n",
    "            stack.append(node)\n",
    "            if node.right:\n",
    "                midPut(node.right)\n",
    "        midPut(root)\n",
    "        start, end = 0, len(stack)-1\n",
    "        while stack[start].val < stack[start+1].val:\n",
    "            start+=1\n",
    "        while stack[end].val > stack[end-1].val:\n",
    "            end-=1\n",
    "        stack[start].val, stack[end].val = stack[end].val, stack[start].val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        prev, first, second = None, None, None\n",
    "        def dfs(node):\n",
    "            nonlocal prev, first, second\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.left)\n",
    "            if not prev:\n",
    "                prev = node\n",
    "            else:\n",
    "                if prev.val > node.val:\n",
    "                    if not first:\n",
    "                        first = prev\n",
    "                        prev = node\n",
    "                        second = node\n",
    "                    else:\n",
    "                        second = node\n",
    "                else:\n",
    "                    prev = node\n",
    "\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        first.val, second.val = second.val, first.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        #时间复杂度O(n) 空间复杂度O(n)\n",
    "        # if not root:\n",
    "        #     return None\n",
    "        # res = []\n",
    "        # def inorder_traverse(node):\n",
    "        #     if not node:\n",
    "        #         return\n",
    "        #     inorder_traverse(node.left)\n",
    "        #     res.append(node)  \n",
    "        #     inorder_traverse(node.right)\n",
    "        # inorder_traverse(root)\n",
    "        # x, y = None, None\n",
    "        # for i in range(len(res)-1):\n",
    "        #     if res[i].val > res[i+1].val:\n",
    "        #         y = res[i+1]\n",
    "        #         if x == None:\n",
    "        #             x = res[i]     \n",
    "        # if x and  y:\n",
    "        #     x.val, y.val = y.val, x.val\n",
    "\n",
    "        #morris traverse 优化空间复杂度O(1)\n",
    "        # x, y, pred = TreeNode(None), TreeNode(None), TreeNode(None)\n",
    "        # while not root:\n",
    "        #     if not root.left:\n",
    "        #         pre = root.left\n",
    "        #         while not pre.right and pre.right != root:\n",
    "        #             pre = pre.right\n",
    "        #         if not pre.right:\n",
    "        #             pre.right = root\n",
    "        #             root = root.left\n",
    "        #         else:\n",
    "        #             if not pred and root.val < pred.val:\n",
    "        #                 y = root\n",
    "        #                 if not x:\n",
    "        #                     x = pred\n",
    "        #             pred = root\n",
    "        #             pre.right = None\n",
    "        #             root = root.right\n",
    "        #     else:\n",
    "        #         if not pred and root.val < pred.val:\n",
    "        #             y = root\n",
    "        #             if not x:\n",
    "        #                 x = pred\n",
    "        #         pred = root\n",
    "        #         root = root.right\n",
    "        # x.val, y.val = y.val, x.val\n",
    "        inorder = lambda x: [] if not x else inorder(x.left) + [x] + inorder(x.right)\n",
    "        a = inorder(root)\n",
    "        sa = sorted(a,key = lambda x: x.val)\n",
    "        p, q = [a[i] for i in range(len(a)) if a[i]!=sa[i]]\n",
    "        p.val, q.val = q.val, p.val\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        def inorder(r: TreeNode) -> List[int]:\n",
    "            return inorder(r.left) + [r] + inorder(r.right) if r else []\n",
    "        re=inorder(root)\n",
    "        # def test(node):\n",
    "        #     if not node.left and not node.right:\n",
    "        #         re.append(node)\n",
    "        #     if node.left:\n",
    "        #         test(node.left)\n",
    "        #     if node.left or node.right:\n",
    "        #         re.append(node)\n",
    "        #     if node.right:\n",
    "        #         test(node.right)\n",
    "        # test(root)\n",
    "        x=y=-1\n",
    "        print(re)\n",
    "        for i in range(len(re)-1):\n",
    "            if re[i+1].val<re[i].val:\n",
    "                y=re[i+1]\n",
    "                if x==-1:\n",
    "                    x=re[i]\n",
    "                else:\n",
    "                    break\n",
    "        temp=x.val\n",
    "        x.val=y.val\n",
    "        y.val=temp\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def iterr(root):\n",
    "    if root.left:\n",
    "        l = iterr(root.left)\n",
    "    else:\n",
    "        l = []\n",
    "    if root.right:\n",
    "        r = iterr(root.right)\n",
    "    else:\n",
    "        r = []\n",
    "    return l + [root, ] + r\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        _list = iterr(root)\n",
    "        n1 = None\n",
    "        for l, r in zip(_list[:-1], _list[1:]):\n",
    "            if l.val > r.val and n1 is None:\n",
    "                n1 = l\n",
    "            if r.val < l.val:\n",
    "                n2 = r\n",
    "        print(_list)\n",
    "        n1.val, n2.val = n2.val, n1.val\n",
    "        return \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        fisrtTreenode = None\n",
    "        secondTreenode = None\n",
    "        pre = TreeNode(-2**31-1)\n",
    "        stack = []\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "\n",
    "            temp = stack.pop()\n",
    "            if not fisrtTreenode and temp.val < pre.val:\n",
    "                fisrtTreenode = pre\n",
    "            if fisrtTreenode and temp.val < pre.val:\n",
    "                secondTreenode = temp\n",
    "            pre = temp\n",
    "            root = temp.right\n",
    "        fisrtTreenode.val, secondTreenode.val = secondTreenode.val, fisrtTreenode.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def recoverTree(self, root):\n",
    "        # Morris\n",
    "        x = y = pre = tmp = None\n",
    "        while root:\n",
    "            if root.left:\n",
    "                tmp = root.left\n",
    "                while tmp.right and tmp.right != root:\n",
    "                    tmp = tmp.right\n",
    "                if not tmp.right:\n",
    "                    tmp.right = root\n",
    "                    root = root.left\n",
    "                else:\n",
    "                    if pre and pre.val>root.val:\n",
    "                        y = root\n",
    "                        if not x:\n",
    "                            x = pre\n",
    "                    pre = root\n",
    "                    tmp.right = None\n",
    "                    root = root.right\n",
    "            else:\n",
    "                if pre and pre.val>root.val:\n",
    "                    y = root\n",
    "                    if not x:\n",
    "                        x = pre\n",
    "                pre = root\n",
    "                root = root.right\n",
    "        if x and y:\n",
    "            x.val, y.val = y.val, x.val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        self.first, self.second = None, None\n",
    "        self.prev = TreeNode(float('-inf'))\n",
    "        def midOrder(node): \n",
    "            if not node: return\n",
    "            midOrder(node.left)\n",
    "            if not self.first and self.prev.val >= node.val:\n",
    "                self.first = self.prev\n",
    "            if self.first and self.prev.val >= node.val:\n",
    "                self.second = node\n",
    "            self.prev = node\n",
    "            midOrder(node.right)\n",
    "        midOrder(root)\n",
    "        self.first.val, self.second.val = self.second.val, self.first.val\n",
    "        \n",
    "# class Solution:\n",
    "#     def recoverTree(self, root: TreeNode) -> None:\n",
    "#         \"\"\"\n",
    "#         Do not return anything, modify root in-place instead.\n",
    "#         \"\"\"\n",
    "#         self.first = self.second = None\n",
    "#         self.prev = TreeNode(float('-inf'))\n",
    "        \n",
    "#         def traverse(node: TreeNode):\n",
    "#             if not node:\n",
    "#                 return\n",
    "#             traverse(node.left)\n",
    "#             if not self.first and self.prev.val >= node.val:\n",
    "#                 self.first = self.prev\n",
    "#             if self.first and self.prev.val >= node.val:\n",
    "#                 self.second = node\n",
    "#             self.prev = node\n",
    "#             traverse(node.right)\n",
    "        \n",
    "#         traverse(root)\n",
    "#         self.first.val, self.second.val = self.second.val, self.first.val\n",
    "# # 99"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        ls = []\n",
    "        def back(r):\n",
    "            if r.left:\n",
    "                back(r.left)\n",
    "            ls.append(r)\n",
    "            if r.right:\n",
    "                back(r.right)\n",
    "        back(root)\n",
    "        for i in range(0, len(ls)-1):\n",
    "            if ls[i].val>ls[i+1].val:\n",
    "                curr_node = ls[i]\n",
    "                break\n",
    "        for i in range(len(ls)-1, 0, -1):\n",
    "            if ls[i].val<ls[i-1].val:\n",
    "                pre_node = ls[i]\n",
    "                break\n",
    "\n",
    "        pre_node.val, curr_node.val = curr_node.val, pre_node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverTree(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        self.first, self.second = None, None\n",
    "        self.prev = TreeNode(float('-inf'))\n",
    "        def midOrder(node): \n",
    "            if not node: return\n",
    "            midOrder(node.left)\n",
    "            if not self.first and self.prev.val >= node.val:\n",
    "                self.first = self.prev\n",
    "            if self.first and self.prev.val >= node.val:\n",
    "                self.second = node\n",
    "            self.prev = node\n",
    "            midOrder(node.right)\n",
    "        midOrder(root)\n",
    "        self.first.val, self.second.val = self.second.val, self.first.val\n",
    "        \n",
    "# class Solution:\n",
    "#     def recoverTree(self, root: TreeNode) -> None:\n",
    "#         \"\"\"\n",
    "#         Do not return anything, modify root in-place instead.\n",
    "#         \"\"\"\n",
    "#         self.first = self.second = None\n",
    "#         self.prev = TreeNode(float('-inf'))\n",
    "        \n",
    "#         def traverse(node: TreeNode):\n",
    "#             if not node:\n",
    "#                 return\n",
    "#             traverse(node.left)\n",
    "#             if not self.first and self.prev.val >= node.val:\n",
    "#                 self.first = self.prev\n",
    "#             if self.first and self.prev.val >= node.val:\n",
    "#                 self.second = node\n",
    "#             self.prev = node\n",
    "#             traverse(node.right)\n",
    "        \n",
    "#         traverse(root)\n",
    "#         self.first.val, self.second.val = self.second.val, self.first.val\n",
    "# # 99"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        switch = [0]*2\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return \n",
    "            else:\n",
    "                dfs(root.left)\n",
    "                ans.append(root)\n",
    "                if len(ans) == 2:\n",
    "                    if ans[0].val >ans[1].val:\n",
    "                        \n",
    "                        try:\n",
    "                            switch[1].val > ans[1].val\n",
    "                            switch[1] = ans[1]\n",
    "                        except:\n",
    "                            switch[0] = ans[0]\n",
    "                            switch[1] = ans[1]\n",
    "                    print(ans[0].val,ans[1].val)\n",
    "                    ans.pop(0)\n",
    "                    \n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        # res = []\n",
    "        # res_ = []\n",
    "        # for node in ans:\n",
    "        #     res.append(node.val)\n",
    "        #     res_.append(node.val)\n",
    "        # res.sort()\n",
    "\n",
    "        # switch = []\n",
    "        # for i in range(len(res_)):\n",
    "        #     if res_[i] != res[i]:\n",
    "        #         switch.append(ans[i])\n",
    "        #         if len(switch) == 2:\n",
    "        #             break\n",
    "        # print(switch[0].val,switch[1].val)\n",
    "       \n",
    "        switch[0].val, switch[1].val  = switch[1].val, switch[0].val\n",
    "    \n",
    "                \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        lst = []\n",
    "        def dfs(root)->None:\n",
    "            if root == None:\n",
    "                return \n",
    "            dfs(root.left)\n",
    "            lst.append(root.val)\n",
    "            dfs(root.right)\n",
    "        begin = deepcopy(root)\n",
    "        dfs(begin)\n",
    "\n",
    "\n",
    "        left,right = -1,-1\n",
    "        for i in range(1, len(lst)):\n",
    "            if lst[i]<lst[i-1]:\n",
    "                right = i\n",
    "                if left == -1:\n",
    "                    left = i-1\n",
    "\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "            \n",
    "            if node.val == lst[right]:\n",
    "                node.val = lst[left]\n",
    "            elif node.val == lst[left]:\n",
    "                node.val =lst[right]\n",
    "            stack.append(node.left)\n",
    "            stack.append(node.right)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        q = list()\n",
    "        cur = root\n",
    "        last, a, b = TreeNode(float(\"-inf\")), None, None\n",
    "\n",
    "        while cur or q:\n",
    "            while cur:\n",
    "                q.append(cur)\n",
    "                cur = cur.left\n",
    "            cur = q.pop()\n",
    "            if not a and last.val > cur.val:\n",
    "                a = last\n",
    "            if a and last.val > cur.val:\n",
    "                b = cur\n",
    "            last = cur\n",
    "            cur = cur.right\n",
    "        a.val, b.val = b.val, a.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        x, y, pre = None, None, None\n",
    "        while len(stack) or root is not None:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "\n",
    "            cur = stack.pop()\n",
    "            if pre and cur.val < pre.val:\n",
    "                y = cur\n",
    "                if x is None:\n",
    "                    x = pre\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            pre = cur\n",
    "            root = cur.right\n",
    "\n",
    "        x.val, y.val = y.val, x.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverTree(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        self.first_node = None\n",
    "        self.second_node = None\n",
    "        self.pre_node = TreeNode(-inf)\n",
    "\n",
    "        def in_order(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            in_order(root.left)\n",
    "            if self.first_node is None and root.val<=self.pre_node.val:\n",
    "                self.first_node = self.pre_node\n",
    "            if self.first_node and root.val<=self.pre_node.val:\n",
    "                self.second_node = root\n",
    "            self.pre_node=root\n",
    "            in_order(root.right)\n",
    "        \n",
    "        in_order(root)\n",
    "        self.first_node.val, self.second_node.val = self.second_node.val, self.first_node.val"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
